package oj;
import java.util.*;

//二叉树的层序遍历：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
public class Solution_102 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root == null){
            return ans;
        }
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> levelQueue = new LinkedList<>();

        nodeQueue.offer(root);
        levelQueue.offer(0);
        //让 preLevel = -1 是为了保证从一开始就和 level 不相同
        int preLevel = -1;
        while(!nodeQueue.isEmpty()){
            TreeNode node = nodeQueue.poll();
            int level = levelQueue.poll();
            if (preLevel != level) {
                //新的一层开始了
                ans.add(new ArrayList<>());//元素类型是 Integer
            }
            //更新 preLevel ，始终让 preLevel 记录上一层遍历的层数
            preLevel = level;
            //每个结点的 level 就刚好对应 ans 中的下标，根据这个下标，就可以获取到对应的 List<Integer> 这层的 List
            //这样就保证了下标不会越界，也就是对应层数的 List<Integer> 一定在 ans 中了
            List<Integer> levelList = ans.get(level);
            //将元素放入对应的 levelList 中(尾插，保证顺序不变)
            levelList.add((int) node.val);
            if(node.left != null){
                nodeQueue.offer(node.left);
                levelQueue.offer(level + 1);
            }
            if(node.right != null){
                nodeQueue.offer(node.right);
                levelQueue.offer(level + 1);
            }
        }
        return ans;
    }
}
